

	ROTI DINTATE - REZOLVARE
       --------------------------

I.MODELAREA PROBLEMEI
----------------------

	Vom atasa ansamblului de roti dintate un graf neorientat cu n varfuri, fiecare varf cores-
punzand unei roti. Intre 2 varfuri vom trasa o muchie daca si numai daca cele 2 roti corespunza-
toare se angreneaza in miscarea de rotatie. Vom considera in continuare ca graful este conex, de-
oarece in caz contrar nu exista solutie: rotirea unei roti nu poate antrena rotirea altei din alta
componenta conexa.
	Graful construit constituie o solutie daca exista o etichetare a varfurilor cu valorile 1
si 2 astfel incat extremitatile oricarei muchii sunt etichetate diferit; intr-adevar, daca 2 roti
vecine, (care se angreneaza) sunt intr-o miscare de rotatie, sensurile lor de rotatie sunt dife-
rite. Observam ca aceasta este echivalent cu oricare dintre conditiile:

(c1) Graful este 2-cromatic (are numarul cromatic egal cu 2), adica putem colora varfurile cu
numai 2 culori astfel incat culorile asociate extremitatilor oricarei muchii sa fie diferite.
(c2) Graful este bipartit, adica exista o partitie a multimii varfurilor V de forma V=V1 U V2
astfel incat oricare muchie sa aiba o extremitate in V1 si cealalta in V2.
(c3) Graful nu contine cicluri de lungime impara; indeplinirea acestei ultime conditii va fi
urmarita in continuare.

	Algoritmul propus presupune determinarea ciclurilor grafului, precum si a punctelor sale
de articulatie. De aceea aceste aspecte vor fi considerate in continuare inainte de prezentarea
algoritmului propriu-zis.

II.DETERMINAREA CICLURILOR ELEMENTARE ALE UNUI GRAF NEORIENTAT
---------------------------------------------------------------

	Fie C multimea ciclurilor elementare ale grafului.
	Fie C(i) multimea ciclurilor elementare in care varful cu numar de ordine maxim este i.
Evident este satisfacuta relatia: C = C1 U C2 U .. U Cn.
	Pe parcursul generarii lui C(i), trebuie sa evitam obtinerea aceluiasi ciclu de mai multe
ori. De aceea se considera in ordine vecinii j ai lui i si se genereaza toate cilurile elementare
(j,i,..,j) in care elementele au numarul de ordine mai mic sau egal cu i. Va fi folosita metoda
backtracking, elementele ciclurilor fiind memorate in vectorul v a carui lungime curenta este no-
tata cu nv.

C = vida
for i=3 to n
    for toti vecinii j ai lui, cu j<i
	v1 <-(j); v(2) <-i; nv<-2; back(2);

procedure back(nv);
k <-v(nv);
for toti s din multimea {1,..,i-1} \ {v(1),..,v(nv)} si s vecin al lui k
	if s=j
	then (v(1),..,v(nv),j) -> C
	else v(nv+1) <- s; back(nv+1);
end

	Performantele algoritmului depind in primul rand de numarul muchiilor grafului. Intr-ade-
var, intr-un graf neorientat complet cu n varfuri nr. ciclurilor elementare este:
	A(n,3) + A(n,4) + .. + A(n,n).
A(p,k) = aranjamente de p luate cate k.
	
III.PUNCTE DE ARTICULATIE
--------------------------

	Intr-un graf neorientat si conex, un varf i se numeste punct de articulatie daca prin inde-
partarea sa si a muchiilor adiacente, graful obtinut nu mai este conex.

	O metoda de determinare a punctelor de articulatie consta in a elimina pe rand din graf
cate un varf al sau si de a determina printr-o parcurger DF daca noul graf este conex.
	Complexitatea aceste metode este O(n^2), dar exista si un algoritm liniar de determinare
a punctelor de articulatie.

IV.PREZENTAREA ALGORITMULUI
----------------------------

Algoritmul urmareste indepartarea unui numar minim de varfuri (impreuna cu muchiile adiacente)
astfel incat graful obtinut sa ramana conex si sa nu contina cicluri de lungime impara.

	Algoritmul urmeaza strategia GREEDY. Se determina varful i cu cele mai multe aparitii in
lista C a ciclurilor de lungime impara; in plus varful i trebuie sa nu fie punct de articulatie,
pt. a fi asigurata conexitatea grafului obtinut prin indepartarea varfului i si a muchiilor adia-
cente. Dupa eliminarea lui i, rationamentul se repeta pentru noul graf pana cand nu mai exista
cicluri de lungime impara sau varfurile tuturor acestor cicluri sunt puncte de articulatie.